#include <iostream>
#include <set>
#include <vector>
#include <queue>
#include <Vector.hpp>

using namespace std;

//fix process: when amount of land larger than 55, id is equal to '1' 

class Solution
{
    vector<pair<int, int>> neighboars = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

public:
    int numIslands(vector<vector<char>> &grid)
    {
        int count = 0;
        for (int x = 0; x < grid[0].size(); x++)
        {
            for (int y = 0; y < grid.size(); y++)
            {
                if (grid[y][x] == '1')
                {
                    floorFill(grid, x, y, '2');
                    // Print2DVector(grid);
                    count++;
                }
            }
        }
        return count;
    }
    void floorFill(vector<vector<char>> &grid, int x, int y, int id)
    {
        if (x >= 0 && x < grid[0].size() && y >= 0 && y < grid.size() && grid[y][x] == '1')
        {
            grid[y][x] = id;
            for (int i = 0; i < 4; i++)
            {
                int newX = x + neighboars[i].first;
                int newY = y + neighboars[i].second;
                floorFill(grid, newX, newY, id);
            }
        }
    }
    /*
    void floorFill(vector<vector<char>> &grid, int x, int y, int id)
    {
        set<pair<int, int>> visited;
        queue<pair<int, int>> waited;
        waited.push({x, y});
        while (!waited.empty())
        {
            grid[waited.front().second][waited.front().first] = id;
            visited.insert(waited.front());
            for (int i = 0; i < 4; i++)
            {
                int newX = waited.front().first + neighboars[i].first;
                int newY = waited.front().second + neighboars[i].second;
                if (newX >= 0 && newX < grid[0].size() && newY >= 0 && newY < grid.size() && grid[newY][newX] == '1')
                {
                    if (visited.count({newX, newY}) == 0)
                    {
                        waited.push({newX, newY});
                    }
                }
            }
            waited.pop();
        }
    }
    */
};

int main()
{
    cout << "Code200" << endl;
    Solution s;
    // vector<vector<char>> grid = {
    //     {'1', '1', '1', '0', '0'},
    //     {'1', '1', '0', '1', '0'},
    //     {'1', '1', '0', '0', '0'},
    //     {'0', '0', '0', '0', '0'}};
    vector<vector<char>> grid = {{'0', '1', '0', '0', '1', '1', '1', '0', '0', '0', '0', '0', '1', '0', '0', '0', '0', '1', '0', '1'},
                                 {'1', '0', '1', '0', '0', '1', '1', '0', '0', '1', '0', '1', '0', '1', '0', '1', '1', '0', '0', '0'},
                                 {'0', '1', '0', '0', '0', '1', '1', '1', '1', '0', '0', '0', '0', '0', '1', '1', '1', '1', '0', '1'},
                                 {'1', '1', '0', '0', '0', '1', '1', '0', '0', '0', '1', '1', '1', '0', '0', '1', '0', '1', '1', '0'},
                                 {'0', '1', '0', '1', '1', '0', '1', '0', '0', '0', '1', '0', '0', '1', '0', '0', '0', '0', '0', '1'},
                                 {'1', '0', '0', '1', '0', '1', '0', '0', '0', '1', '1', '0', '1', '0', '0', '1', '0', '0', '0', '0'},
                                 {'1', '0', '0', '0', '1', '1', '0', '0', '0', '0', '0', '1', '0', '0', '1', '0', '0', '0', '0', '1'},
                                 {'1', '0', '0', '0', '1', '0', '1', '1', '1', '0', '1', '0', '1', '1', '1', '1', '0', '0', '0', '1'},
                                 {'1', '0', '0', '1', '0', '0', '0', '1', '0', '0', '0', '0', '0', '0', '0', '0', '0', '1', '0', '1'},
                                 {'0', '0', '0', '1', '0', '1', '1', '1', '1', '1', '1', '1', '1', '1', '0', '0', '0', '0', '1', '0'},
                                 {'1', '0', '1', '0', '1', '0', '0', '1', '1', '1', '0', '1', '1', '0', '0', '1', '1', '0', '0', '0'},
                                 {'0', '1', '0', '0', '1', '0', '0', '0', '0', '0', '0', '1', '1', '1', '1', '0', '0', '0', '1', '0'},
                                 {'1', '0', '0', '0', '1', '1', '1', '0', '1', '0', '0', '0', '1', '0', '1', '0', '1', '0', '0', '1'},
                                 {'0', '0', '0', '0', '1', '0', '1', '1', '0', '1', '0', '1', '0', '1', '1', '1', '1', '0', '0', '0'},
                                 {'0', '1', '1', '0', '0', '0', '0', '1', '0', '0', '1', '1', '1', '0', '0', '1', '1', '0', '1', '0'},
                                 {'1', '0', '1', '1', '1', '1', '1', '1', '0', '1', '1', '0', '1', '0', '0', '1', '0', '0', '0', '1'},
                                 {'1', '0', '0', '0', '1', '0', '1', '0', '0', '1', '0', '1', '0', '0', '1', '0', '0', '1', '1', '1'},
                                 {'0', '0', '1', '0', '0', '0', '0', '1', '0', '0', '1', '1', '0', '1', '1', '1', '0', '0', '0', '0'},
                                 {'0', '0', '1', '0', '0', '0', '0', '0', '0', '1', '1', '0', '1', '0', '1', '0', '0', '0', '1', '1'},
                                 {'1', '0', '0', '0', '1', '0', '1', '1', '1', '0', '0', '1', '0', '1', '0', '1', '1', '0', '0', '0'}};
    cout << s.numIslands(grid) << endl;
    return 0;
}
